package top101K.linkedList;

/**
 * @Author quan
 * @Description 两个链表的第一个公共结点
 * @Date 2023/7/30 22:08
 */
public class Demo10_FindFirstCommonNode {
    /**
     * 双循环：8/9的测试通过（自己的做法）
     * @param pHead1 子链表1的头结点
     * @param pHead2 子链表2的头结点
     * @return 两者的公共链表部分
     */
//    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//        ListNode cur1 = pHead1;
//        ListNode cur2 = pHead2;
//        ListNode common = cur1;
//        //base case
//        if (pHead1 == null) {
//            return null;
//        } else if (pHead2 == null) {
//            return null;
//        } else {
//            //common case
//            while (cur1 != null) {
//                while (cur2 != null) {
//                    if (cur1.val == cur2.val) {
//                        common = cur2;
//                        return common;
//                    }
//                    cur2 = cur2.next;
//                }
//                cur1 = cur1.next;
//                cur2 = pHead2;
//            }
//            return null;
//        }
//    }

    /**
     * 参考答案解题：双指针:巧解
     * cur1从链表1开始走，cur2从链表2开始走，当cur1走完子链表1的时候，开始从链表2走；同理cur2走完子链表1，
     * 就从链表1开始走。因为两个走的路径是一样的，都是链表1+链表2的长度，所以相同的路径和速度，这两个指针最后
     * 一定能走到终点。此时在他们两个相遇的节点就是公共节点。
     * @param pHead1  链表1的头结点
     * @param pHead2  链表2的头结点
     * @return
     */
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode cur1 = pHead1;
        ListNode cur2 = pHead2;
        while (cur1!=cur2){
            cur1 = cur1==null?pHead2:cur1.next;
            cur2 = cur2==null?pHead1:cur2.next;
        }
        return cur1;
    }
}
